package com.wyw.leetcode.learning.medium;

import com.wyw.leetcode.simple.parent.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * leetcode topic 142
 * 环形列表2
 *
 * @Author Mr Wu    yewen.wu.china@gmail.com
 * <p>
 * Update History:
 * Author        Time            Content
 */
public class Topic142 {
    public static void main(String[] args) {

    }

    /**
     * 哈希表
     * @param head
     * @return
     */
    public static ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> set = new HashSet<>();
        while (pos != null) {
            if (set.contains(pos)) {
                return pos;
            } else {
                set.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }

    /**
     * 双指针
     */
    public static ListNode detectCycle1(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}
